package com.cdream.basic.algorithm.leetcode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author cdream
 * @date 7/16/21
 */
public class BinarySearch {
    /**
     * 可以查询高低的2分查找法
     */
    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[ans] == target ? ans : -1;
    }

    /**
     * 普通二分
     */
    public int binarySearch(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        while (end >= start) {
            int mid = start + (end - start) / 2;

            if (nums[mid] > target) {
                end = mid - 1;
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    public int binarySearchLeft(int[] nums, int target) {
        int start = 0, end = nums.length - 1;
        while (end > start) {
            int mid = start + end >> 1;
            if (nums[mid] >= target) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return target == nums[start] ? start : -1;
    }

    public int binarySearchRight(int[] nums, int target) {
        int start = 0, end = nums.length - 1;
        while (end > start) {
            int mid = start + end + 1 >> 1;
            if (nums[mid] <= target) {
                start = mid;
            } else {
                end = mid - 1;
            }
        }
        return target == nums[end] ? end : -1;
    }

    public static void main(String[] args) {
        System.out.println(new BinarySearch().binarySearchLeft(new int[]{1, 2, 2, 4, 4}, 2));
        System.out.println(new BinarySearch().binarySearchRight(new int[]{1, 2, 2, 4, 4}, 2));
        System.out.println("ab".substring(2));
        System.out.println(reorderedPowerOf2(1));
    }
    public static boolean reorderedPowerOf2(int n) {
        Set<String> s = new HashSet<>();
        for(int i = 0; i<=31; i++){
            char[] charArray = String.valueOf((int) Math.pow(2, i)).toCharArray();
            Arrays.sort(charArray);
            s.add(new String(charArray));
        }
        char[] res = String.valueOf(n).toCharArray();
        Arrays.sort(res);
        return s.contains(new String(res));
    }
}
